package th.retrofit.lib;

import java.util.ArrayList;
import java.util.List;
import java.util.StringJoiner;
import java.util.stream.Collectors;

/**
 * https://leetcode-cn.com/problems/restore-ip-addresses/
 * 给定一个只包含数字的字符串，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
 *
 * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 *
 * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
 *
 */
public class Solution93 {

    public List<String> restoreIpAddresses(String s) {
        List<String> results = new ArrayList<>();
        List<String> sub = new ArrayList<>(4);
        int sLen = s.length();
        int min = sLen / 4;
        if (min < 1 || min > 3) return results;
        backtrack(results, sub, s, 0);
        return results;
    }

    private void backtrack(List<String> results, List<String> sub, String s, int index) {
        if (index == s.length() && sub.size() == 4) {
            results.add(list2ip(sub));
            return;
        }
        final int sLen = s.length();
        if (((4 - sub.size()) * 3) < sLen - index) return;
        for (int i = index + 1; i <= sLen && i <= index + 3; i++) {
            String part = s.substring(index, i);
            if (part.charAt(0) == '0' && i - index > 1) continue;
            if (Integer.parseInt(part) > 255) continue;
            sub.add(part);
            backtrack(results, sub, s, i);
            sub.remove(sub.size() - 1);
        }
    }

    private String list2ip(List<String> strings) {
        return String.join(".", strings);
    }

    public static void main(String[] args) {
//        List<String> sub = new ArrayList<>();
//        sub.add("255");
//        sub.add("255");
//        sub.add("0");
//        sub.add("255");
//        System.out.println(String.join(".", sub));
//        System.out.println("absde".substring(0, 2));
        List<String> results = new Solution93().restoreIpAddresses("172162541");
        results.forEach(System.out::println);
    }

}
